package main.Q1001_1100;

import java.util.*;

public class Q1001_1010 {
    public static void main(String[] args) {
        System.out.println("Question1001：");
        System.out.println("Question1002：查找共用字符");
        System.out.println("Question1003：");
        System.out.println("Question1004：");
        System.out.println("Question1005：K次取反后最大化的数组和");
        System.out.println("Question1006：笨阶乘");
        System.out.println("Question1007：");
        System.out.println("Question1008：前序遍历构造二叉搜索树");
        System.out.println("Question1009：");
        System.out.println("Question1010：总持续时间可被 60 整除的歌曲");
        int[] times = new int[]{30,20,150,100,40};
        System.out.println(new Question1010().numPairsDivisibleBy60(times));
    }
}

class Question1002 {
    public List<String> commonChars(String[] words) {
        int[][] counts = new int[words.length][26];
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                counts[i][words[i].charAt(j) - 'a']++;
            }
        }
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < words.length; j++) {
                min = Math.min(min, counts[j][i]);
            }
            for (int k = 0; k < min; k++) {
                result.add(String.valueOf((char) ('a' + i)));
            }
        }
        return result;
    }
}

class Question1005 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {//将负数取反
            if (nums[i] <= 0 && k > 0) {
                nums[i] = nums[i] * -1;
                k--;
            }
        }
        if (k != 0) {
            Arrays.sort(nums);
            while (k > 0) {
                nums[0] = nums[0] * -1;
                k--;
            }
        }
        for (int num : nums) sum += num;
        return sum;
    }
}

class Question1006 {
    public int clumsy(int n) {
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(n);
        n--;
        int index = 0;
        while (n > 0) {
            if (index % 4 == 0) {
                stack.push(stack.pop() * n);
            } else if (index % 4 == 1) {
                stack.push(stack.pop() / n);
            } else if (index % 4 == 2) {
                stack.push(n);
            } else {
                stack.push(-n);
            }
            index++;
            n--;
        }
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        return result;
    }
}

class Question1008 {
    public TreeNode process(int[] preorder, int left, int right) {
        TreeNode curNode = new TreeNode(preorder[left]);
        int mid = left;
        for (int i = left + 1; i <= right; i++) {
            if (preorder[i] < preorder[left]) {
                mid++;
            } else {
                break;
            }
        }
        if (mid > left) {
            curNode.left = process(preorder, left + 1, mid);
        }
        if (mid < right) {
            curNode.right = process(preorder, mid + 1, right);
        }
        return curNode;
    }

    public TreeNode bstFromPreorder(int[] preorder) {
        return process(preorder, 0, preorder.length - 1);
    }
}

class Question1010 {
    public int numPairsDivisibleBy60(int[] time) {
        int[] counts = new int[60];
        for (int t : time) {
            counts[t % 60]++;
        }
        long result = 0;
        for (int i = 1; i < 30; i++) {
            result += counts[i] * counts[60 - i];
        }
        result += (long) counts[0] * (counts[0] - 1) / 2 + (long) counts[30] * (counts[30] - 1) / 2;
        return (int) result;
    }
}